#include<bits/stdc++.h>
#define rg register
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

const int maxn=1e6+10;

int n,Q;
char S[maxn];

inline int solve(int l,int r)
{
	static int A[maxn];int top=0;
	int pre=0,re=0;
	for(rg int i=l;i<=r;i+=1)
	{
		if(pre==0&&S[i]=='0')
		{
			A[++top]=1,A[++top]=0;
			re+=1;
			continue;
		}
		A[++top]=S[i]-'0';
		pre+=(S[i]=='1'?1:-1);
	}
	pre=0;
	for(rg int i=top;i;i-=1)
	{
		if(pre==0&&A[i]==0)
		{
			re+=1;
			continue;
		}
		pre+=A[i]==1?1:-1;
	}
	return re;
}

int main()
{
//	file("good1");
	scanf("%d %d",&n,&Q);
	scanf("%s",S+1);
	int Ans=0;
	while(Q--)
	{
		int l,r;scanf("%d %d",&l,&r);
		int re=solve(l,r);
		Ans^=re;
		cout<<re<<endl;
	}
	cout<<endl;
	printf("%d\n",Ans);
	return 0;
}
